package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 不同路径   排列组合 C₅³=5×4×3/3×2×1=10  不考虑顺序
 * @date 2022/8/13 17:27
 */
public class Demo20 {
    public static void main(String[] args) {
        int i = uniquePaths(10, 10);
        System.out.println(i);
    }
    public static int uniquePaths(int m, int n) {
        int fenmu=m+n-2;
        int fenzi=Math.min(m-1,n-1);
        long sum1=1;
        long sum2=1;
       while (fenzi>0){
           sum1*=fenmu;
           sum2*=fenzi;

           if(sum1%fenzi==0){
               sum1/=fenzi;
               sum2/=fenzi;
           }
           if(sum1%sum2==0){
               sum1/=sum2;
               sum2/=sum2;
           }
           fenzi--;
           fenmu--;
       }
       return (int) (sum1/(sum2));
    }
}
